package com.leetcode;

import ds.TreeNode;

/**
 * TODO
 *
 * @author lefly
 * @version 1.0
 * @classname No236
 * @description 236. 二叉树的最近公共祖先
 * @date 2021/1/29 下午12:18
 */
public class No236 {
    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        TreeNode t4 = new TreeNode(4);
        TreeNode t5 = new TreeNode(5);
        TreeNode t6 = new TreeNode(6);
        TreeNode t7 = new TreeNode(7);
        TreeNode t8 = new TreeNode(8);
        TreeNode t9 = new TreeNode(9);

        t1.left = t2;
        t1.right = t3;
        t2.left = t4;
        t4.right = t5;
        t3.left = t6;
        t6.right = t7;
        t7.right = t8;
        t8.left = t9;

        TreeNode res = lowestCommonAncestor(t1,t6,t7);
        System.out.println(res.val);
    }

    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || p == root || q == root){
            return root;
        }
        TreeNode leftNode = lowestCommonAncestor(root.left,p,q);
        TreeNode rightNode = lowestCommonAncestor(root.right,p,q);
        if(leftNode == null){
            return rightNode;
        }
        if(leftNode != null && rightNode != null){
            return root;
        }
        return leftNode;

    }

}
